package com.bondar.task2;


public class MergeSort<T extends Comparable<T>> implements Runnable {
	private T[] arr;
	private int left;
	private int right;

	public MergeSort(T[] arr, int l, int r) {
		this.arr = arr;
		left = l;
		right = r;
	}

	/**
	 * Merge-Sort with concurrency
	 * 
	 * @param arr
	 * @param threads
	 * @param length 
	 */
	public static <T extends Comparable<T>> void sort(T[] arr,int left, int right) {
		if (left < right) {
			int middle = (left + right) / 2;
			Thread threadLeft = new Thread(new MergeSort(arr, left, middle));
			
			threadLeft.start();
			sort(arr, middle+1, right);
			
			try {
				threadLeft.join();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}

			// merge
			T[] aux =  (T[]) new Comparable [arr.length];
			MergeSort.merge(arr, aux, left, middle, right);
		}
		

	}
	
	private static <T extends Comparable<T>> void merge(T[] arr, T[] aux , int left, int middle, int right) {
		// copy arr to aux
		for (int i = left; i <= right; i++) {
			aux[i] = arr[i];
		}
		
		int i = left, j = middle + 1;
		for (int k = left; k <= right; k++) {
			// left side come over middle -> move j right
			if (i > middle) {
				arr[k] = aux[j++];
				continue;
			}
			if (j > right) {
				arr[k] = aux[i++];
				continue;
			}
			// if aux[j] < aux[i]
			else if (aux[j].compareTo((T) aux[i]) < 0) {
				arr[k] = aux[j++];
				continue;
			} else
				arr[k] = aux[i++];
		}
	}

	@Override
	public void run() {
		sort(arr, left, right);
	}

}

